package leetcode_day._2021._202112._2131;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/28 9:30
 * 连接词
 * 给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
 * 连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
 * 算法：字典树 + 深度优先搜索
 * 先将数组按照单词长度从小到大排序
 * 遍历数组，先使用 dfs 判断这个单词能否使用其他单词组成
 * 如果可以，那么就不放入字典树, 因为已经在字典树中了；反之，则放入
 */
public class _28_472 {
    Trie trie = new Trie();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> ans = new ArrayList<>();
        Arrays.sort(words, Comparator.comparingInt(String::length));
        for (String word : words) {
            if (dfs(word, 0)) ans.add(word);
            else trie.insert(word);
        }
        return ans;
    }
    boolean dfs(String word, int start) {
        if (word.length() == start) return !"".equals(word);
        Trie cur = trie;
        for (int i = start; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            cur = cur.children[idx];
            if (cur == null) return false;
            if (cur.isEnd) if (dfs(word, i + 1)) return true;
        }
        return false;
    }
    class Trie {
        Trie[] children;
        boolean isEnd;
        Trie() {
            children = new Trie[26];
            isEnd = false;
        }
        void insert(String word) {
            Trie cur = this;
            for (int i = 0; i < word.length(); i++) {
                int idx = word.charAt(i) - 'a';
                if (cur.children[idx] == null) cur.children[idx] = new Trie();
                cur = cur.children[idx];
            }
            cur.isEnd = true;
        }
    }

}
